{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7550ffd5-a643-4644-be9e-700dcbe95bf3",
   "metadata": {},
   "source": [
    "# 198. 打家劫舍\n",
    "\n",
    "你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。\n",
    "\n",
    "给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "> 输入：[1,2,3,1]  \n",
    "> 输出：4  \n",
    "> 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。  \n",
    ">      偷窃到的最高金额 = 1 + 3 = 4 。\n",
    "\n",
    "示例 2：\n",
    "\n",
    "> 输入：[2,7,9,3,1]  \n",
    "> 输出：12  \n",
    "> 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。  \n",
    ">      偷窃到的最高金额 = 2 + 9 + 1 = 12 。\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "> 1 <= nums.length <= 100  \n",
    "> 0 <= nums[i] <= 400  "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9e561dbb-84b8-4dd6-99f7-fc2d4aa0f287",
   "metadata": {},
   "source": [
    "# 1、暴⼒递归"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "79686612-6ade-419a-85fd-54c817e10e06",
   "metadata": {},
   "source": [
    "1 if n = 0 then // 基本情况1  \n",
    "2 return 空集  \n",
    "3 if n = 1 then // 基本情况2  \n",
    "4 return { $v_1$ }  \n",
    "// 当n ≥ 2时进行递归  \n",
    "5 $S_1$ := 递归地计算 $G_{n−1}$ 的MWIS  \n",
    "6 $S_2$ := 递归地计算 $G_{n−2}$ 的MWIS  \n",
    "7 return $S_1$ 或 $S_2 \\cup {v_n}$ 中权重更大的那个"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "46454f15-5eb3-465d-98dd-22f1fb35016e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rob_helper(nums, n):\n",
    "    if n == 0: \n",
    "        return []\n",
    "    if n == 1:\n",
    "        return [nums[0]]\n",
    "\n",
    "    s1 = rob_helper(nums, n-1)\n",
    "    s2 = rob_helper(nums, n-2)\n",
    "    if sum(s1) > sum(s2) + nums[n-1]:\n",
    "        return s1\n",
    "    else:\n",
    "        return s2 + [nums[n-1]]\n",
    "\n",
    "def rob(nums):\n",
    "    return rob_helper(nums, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0585190a-b19b-4b0d-b872-5d32012ef8bb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s:  [1, 3]\n",
      "sum:  4\n"
     ]
    }
   ],
   "source": [
    "s = rob([1, 2, 3, 1])\n",
    "print(\"s: \", s)\n",
    "print(\"sum: \", sum(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0ce5bcf8-1232-4f92-9eb5-e860a5e62ac6",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s:  [2, 9, 1]\n",
      "sum:  12\n"
     ]
    }
   ],
   "source": [
    "s = rob([2, 7, 9, 3, 1])\n",
    "print(\"s: \", s)\n",
    "print(\"sum: \", sum(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d28b2bbe-1a9d-496d-bdf2-c1aa244df43f",
   "metadata": {},
   "source": [
    "## 2、带备忘录的递归"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "00527486-9e44-43d1-8710-80e312d00816",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rob_helper(memo, nums, n):\n",
    "    # 查备忘录，避免重复计算\n",
    "    if n in memo: return memo[n]\n",
    "        \n",
    "    if n == 0:\n",
    "        memo[0] = []\n",
    "        return []\n",
    "    if n == 1:\n",
    "        memo[1] = [nums[0]]\n",
    "        return [nums[0]]\n",
    "\n",
    "    s1 = rob_helper(memo, nums, n-1)\n",
    "    s2 = rob_helper(memo, nums, n-2)\n",
    "    if sum(s1) > sum(s2) + nums[n-1]:\n",
    "        memo[n] = s1\n",
    "        return s1\n",
    "    else:\n",
    "        memo[n] = s2\n",
    "        return s2 + [nums[n-1]]\n",
    "\n",
    "def rob(nums):\n",
    "    memo = dict()\n",
    "    return rob_helper(memo, nums, len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "9e2922aa-d231-468c-a952-ab24cdc98f47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s:  [1, 3]\n",
      "sum:  4\n"
     ]
    }
   ],
   "source": [
    "s = rob([1, 2, 3, 1])\n",
    "print(\"s: \", s)\n",
    "print(\"sum: \", sum(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "9387e8d6-21a5-4cb5-8867-65b085d438af",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s:  [2, 9]\n",
      "sum:  11\n"
     ]
    }
   ],
   "source": [
    "s = rob([2, 7, 9, 3, 1])\n",
    "print(\"s: \", s)\n",
    "print(\"sum: \", sum(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b78def92-2e21-4a8a-afa2-9958288c5c77",
   "metadata": {},
   "source": [
    "## 3、dp 数组的迭代解法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "3f2ef2ae-a856-4477-9cfa-86be859e370c",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rob(nums):\n",
    "    dp = [0] * (len(nums)+1)\n",
    "\n",
    "    dp[0] = 0\n",
    "    dp[1] = nums[0]\n",
    "    \n",
    "    for i in range(2, len(nums)+1):\n",
    "        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])\n",
    "\n",
    "    return dp[len(nums)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "b0a18b3b-08fc-4fbf-ac01-1e7021cb754c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "12\n"
     ]
    }
   ],
   "source": [
    "print(rob([1, 2, 3, 1]))\n",
    "print(rob([2, 7, 9, 3, 1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5256a62d-526d-431c-8772-2a0db5c7e04d",
   "metadata": {},
   "source": [
    "## 4、一种重建算法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "ebe2697a-ff1a-4ff2-938f-9c4ff63fc8a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def rob(nums):\n",
    "    dp = [0] * (len(nums)+1)\n",
    "\n",
    "    dp[0] = 0\n",
    "    dp[1] = nums[0]\n",
    "    \n",
    "    for i in range(2, len(nums)+1):\n",
    "        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])\n",
    "\n",
    "    i = len(nums)\n",
    "    s = []\n",
    "    while i >= 2:\n",
    "        if dp[i-1] > dp[i-2]+nums[i-1]:\n",
    "            i = i - 1\n",
    "        else:\n",
    "            s.append(nums[i-1])\n",
    "            i = i - 2\n",
    "\n",
    "    if i == 1:\n",
    "        s.append(nums[0])\n",
    "\n",
    "    return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "08661699-8aec-4b12-b360-fbd1625f9382",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s:  [3, 1]\n",
      "sum:  4\n"
     ]
    }
   ],
   "source": [
    "s = rob([1, 2, 3, 1])\n",
    "print(\"s: \", s)\n",
    "print(\"sum: \", sum(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "8264f67a-910f-4563-a164-5d18f834b5c3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s:  [1, 9, 2]\n",
      "sum:  12\n"
     ]
    }
   ],
   "source": [
    "s = rob([2, 7, 9, 3, 1])\n",
    "print(\"s: \", s)\n",
    "print(\"sum: \", sum(s))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e8acd77e-8659-4654-bea6-dd07ab90c521",
   "metadata": {},
   "source": [
    "参考资料：\n",
    "- 《算法详解（卷3）——贪心算法和动态规划》：4.1 加权独立集合问题"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
